package 动态规划.背包问题;

/**
 * @ClassName _474一和零
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2022/1/5 20:19
 * Version 1.0
 **/
public class _474一和零 {
    public int findMaxForm(String[] strs, int m, int n) {//相当于两个维度得背包！！！！
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
